package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 基数排序</p>
 *
 * @author tanzc
 * @date 2022/1/28
 **/
public class RadixSort {

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int num = 100000000, max = num * 5;
        int[] arr = ArrayUtils.randomoffset(num, max, 100);
//        int[] arr = ArrayUtils.worst(num);
//        int[] arr = ArrayUtils.bad(num);
//        int[] arr = ArrayUtils.nice(num);

        int[] arr1 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
//        ArrayUtils.printArray(arr1);

        System.out.print("基数排序-----time: ");
        Date start = new Date();
        int[] arr2 = radixSort.radix(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        ArrayUtils.printArray(arr2);
    }

    /**
     * 基数排序
     * 同样不是基于元素比较，而是依据元素值特征的选择
     * 按最大元素的位数，每一轮基数按个、十、百等基数位选择，相同基数的放入一个数组，再按基数数组放入原数组
     * 经过若干轮选择，最新的数组将有序
     * @param arr
     * @return
     */
    public int[] radix(int[] arr) {
        int max = Integer.MIN_VALUE;
        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        // 基数数组桶
        int[][] temp = new int[10][arr.length];
        // 记录每个桶中元素数
        int[] counts = new int[10];
        int maxLen = (max + "").length();
        // 基数排序，按最大数的位数确定排序轮数
        // 每选择一轮，n *= 10，即下一轮获取的基数为下一进制位上的
        for (int k = 0, n = 1; k < maxLen; k++, n *= 10) {
            for (int i = 0; i < arr.length; i++) {
                // 获取基数
                int base = arr[i] / n % 10;
                // 这里使用counts数组记录每个基数数组内的元素数
                // 因为使用的是原始的数组，添加元素需要在指定索引位置，不能像List这些可以直接添加
                temp[base][counts[base]] = arr[i];
                counts[base]++;
            }

            // 将一轮基数选择后的放入原数组
            int index = 0;
            // 对counts遍历，就相当于在对temp的第一个纬度即行遍历，这里counts.length直接换成10更好理解
            for (int l = 0; l < counts.length; l++) {
                // 该基数的数组内有值
                if (counts[l] != 0) {
                    for (int j = 0; j < counts[l]; j++) {
                        arr[index++] = temp[l][j];
                    }
                    counts[l] = 0;
                }
            }
        }

        return arr;
    }

    public int[] radixSort(int[] arr) {
        //求出数组中的最大值
        int max = Integer.MIN_VALUE;
        int[] result = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
//        System.out.println(max);
        //定义存取取余之后的数字 10代表0-9的基数 arr.length 代表每个技术组中最多存的元素
        int[][] temp = new int[10][arr.length];
        //定义一个记录每个基数组中所存数字个数 因为基数就10个 0-9
        int[] counts = new int[10];
        //获取最大数字的位数
        int maxLen = (max + "").length();
        //maxLen 决定要排几次序
        for (int k = 0, n = 1; k < maxLen; k++, n *= 10) {
            //取模求出基数
            for (int p = 0; p < arr.length; p++) {
                //获取该数字的基数
                int sr = arr[p] / n % 10;
                //counts[sr] 这个基数组 初始值是0 进去一个 counts[sr]++
                temp[sr][counts[sr]] = arr[p];
                counts[sr]++;
            }
//            if(k==0){
//                for (int [] u:temp) {
//                    System.out.println("--"+Arrays.toString(u));
//                }
//            }

            //记录原数组下标
            int index = 0;
            //取出存入的数字放入原数组
            for (int l = 0; l < counts.length; l++) {
                //计入记录的数组当前值不为0
                if (counts[l] != 0) {
                    //循环取出数字
                    for (int o = 0; o < counts[l]; o++) {
                        arr[index++] = temp[l][o];
                    }
                    //将记录变为0
                    counts[l] = 0;
                }
            }
            //这里可以不清空，赋值覆盖之气那的数组就行了，不过数据不好查看
//            temp=new int[10][arr.length];
        }


        return arr;
    }
}
